#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;




struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left),
         right(right) {}
    
};
class Solution {
public:
    TreeNode* answer(vector<int>& preorder, vector<int>& inorder, int& t,
        int lefti, int righti) {
        if (lefti > righti) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[t]);

        int v = lefti;
        while (v <= righti) {
            if (inorder[v] == preorder[t]) {
                break;
            }
            v++;
        }
        t++;
        root->left = answer(preorder, inorder, t, lefti, v - 1);
        root->right = answer(preorder, inorder, t, v + 1, righti);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return answer(preorder, inorder, i, 0, inorder.size() - 1);
    }
};
int main()
{
    vector<int> h = { 3, 9, 20, 15, 7 };
    vector<int> h1 = { 9,3,15,20,7 };

    Solution t;
    t.buildTree(h, h1);

};
